4. Median of Two Sorted Arrays

這題的目的是要在兩個已排序的陣列nums和nums2中，找到它們合併後的中位數。這題的困難點在於，它要求在O(log(m + n))的時間複雜度內完成，所以不能直接將兩個陣列合併後排序。

這題的核心概念在於中位數與分割線，為了要在兩個排序陣列中找到中位數，要找到一條｢分割線｣，將這兩個陣列的所有元素分割成兩半，使左半邊的元素都小於或等於右半邊的元素，如果元素總數是奇數的話，中位數就是中間那個元素，如果是偶數的話，中位數就是中間兩個元素的平均。這條分割線會滿足兩個條件：1.分割後左右兩邊的元素數量相等，左半邊的元素數量(m + n + 1) / 2。2.左半邊的最大值小於或等於右半邊的最小值:max(left_part)<=min(right_part)。

這題的解題思路是利用二分法，因為陣列是已經排序好的。目標是在較短的陣列（假設為nums1）上進行二分搜尋，來找到最佳的分割點i。首先要先處理陣列長度問題，為了簡化問題，要始終在較短的陣列進行二分搜尋。假設nums1的長度m小於或等於nums2的長度n，如果不是，就交換它們。接著，就要進行二分搜尋，在nums1的範圍[0, m]內進行二分搜尋，選擇一個分割點i。將這條分割線將nums1分成nums1[0…i-1]和nums1[i…m-1]。再來，要計算另一條陣列的分割點，因為左右兩邊的總元素數量是固定的(m + n + 1) / 2，所以在確定nums1的分割點是i後，nums2的分割點j也就確定了：j = (m + n + 1) / 2 - i。找到分割點後，需要檢查它們，我現在找到了四個值：nums1_left：nums1[i-1]（如果i > 0）、nums1_right：nums1[i]（如果i < m）、nums2_left：nums2[j-1]（如果j > 0）和nums2_right：nums2[j]（如果j < n）。需要檢查nums1_left <= nums2_right且nums2_left <= nums1_right是否成立，如果nums1_left > nums2_right，說明nums1的分割點太大了，需要向左移動，所以high = i - 1。如果nums2_left > nums1_right，說明nums1的分割點太小了，需要向右移動，所以low = i + 1。最後，找到一個滿足條件的i時，就等於找到了最佳分割線。左半邊的最大值是max(nums1_left, nums2_left)，右半邊的最小值是min(nums1_right, nums2_right)，如果總元素是奇數，中位數就是左半邊的最大值，如果總元素是偶數，中位數就是左半的最大值和右半邊的最小值的平均值。

我寫的程式碼是透過二分法不斷調整nums1的分割點i，並根據nums2的分割點j進行檢查。每次檢查都將搜尋範圍縮小一半，最終達到O(log(min(m, n)))的時間複雜度，也就是O(log(m + n))。